package main

import (
	"fmt"
	"sort"
)

func main() {
	//基础题
	//01.go实现 while 循环实现输出2 - 3 + 4 - 5 + 6 ... + 100 的和
	fmt.Println("01.go实现 while 循环实现输出2 - 3 + 4 - 5 + 6 ... + 100 的和")
	w := 2
	sum := 0
	for {
		if w > 100 {
			break
		}
		if w%2 == 0 {
			sum += w
			//fmt.Println(sum)
		} else {
			sum -= w
		}
		w++
	}
	fmt.Println(sum)

	//02.for循环实现九九乘法表
	fmt.Println("02.for循环实现九九乘法表")
	for i := 1; i <= 9; i++ {
		for j := 1; j <= i; j++ {
			fmt.Printf("%v * %v = %-2v ", j, i, i*j)
		}
		fmt.Println()
	}

	//03.golang实现冒泡排序
	fmt.Println("03.golang实现冒泡排序")
	arr := []int{11, 8, 2, 5, 7, 10, 3, 6}
	for i := 0; i < len(arr)-1; i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j+1] < arr[j] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	fmt.Println(arr)

	//04.golang实现快排
	fmt.Println("04.golang实现快排")
	arr2 := []int{10, 7, 8, 9, 1, 5}
	quickSort(arr2, 0, len(arr2)-1)
	fmt.Println("Sorted array:", arr2)

	//05.判断101-200之间有多少个素数，并输出所有素数
	fmt.Println("05.判断101-200之间有多少个素数，并输出所有素数")
	var arr1 []int
	for i := 101; i <= 200; i++ {
		if i%2 != 0 {
			arr1 = append(arr1, i)
		}
	}
	fmt.Printf("有%v个素数分别为：%v\n", len(arr1), arr1)

	//06.实现map的有序遍历
	fmt.Println("06.实现map的有序遍历")
	var userInfo = map[string]string{
		"username": "root",
		"password": "123456",
		"sex":      "male",
		"age":      "18",
	}
	// 收集所有 key
	keys := make([]string, 0, len(userInfo))
	for k := range userInfo {
		keys = append(keys, k)
	}
	// 对 key 排序
	sort.Strings(keys)
	// 按排序后的 key 遍历 map
	for _, k := range keys {
		fmt.Printf("%s: %s\n", k, userInfo[k])
	}

	//07.字符串反转
	fmt.Println("07.字符串反转")
	str := "Hello, 世界"
	runes := []rune(str)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	fmt.Println(string(runes))

	//08.合并两个有序列表
	fmt.Println("08.合并两个有序列表")
	a := []int{1, 3, 8}
	b := []int{4, 5, 9}
	merged := mergeSortedSlices(a, b)
	fmt.Println("合并后的列表:", merged)

	//进阶题
	//01.找最长公共前缀
	//编写一个函数来查找字符串数组中的最长公共前缀。
	//如果不存在公共前缀，返回空字符串 "" 。
	//	输入：strs = ["flower","flow","flight"]
	//	输出："fl"
	//
	//	输入：strs = ["dog","racecar","car"]
	//	输出：""
	//	解释：输入不存在公共前缀。
	var s1 = [...]string{"flower", "flow", "flight"}
	for i := 0; i < len(s1); i++ {
		fmt.Println(s1[i])
		//for i := 0; i < len(s1[i]); i++ {
		//	fmt.Println(i)
		//}
	}

	//02.字符串压缩
	//字符串压缩，利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。
	//若“压缩”后的字符串没有变短，则返回原先的字符串。
	//你可以假设字符串中只包含大小写英文字母（a至z）。
	//	输入："aabcccccaaa"
	//	输出："a2b1c5a3"
	//
	//	输入："abbccd"
	//	输出："abbccd"
	//	解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。
}

//冒泡排序
func bubbleSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	}
	for i := 0; i < length-1; i++ {
		for j := 0; j < length-i-1; j++ {
			if arr[j+1] > arr[j] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
	return arr
}

// 快速排序函数
func quickSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	i, j := left, right
	pivot := arr[left] // 选择最左边作为基准值

	for i < j {
		// 从右往左找小于 pivot 的值
		for i < j && arr[j] >= pivot {
			j--
		}
		arr[i] = arr[j]

		// 从左往右找大于 pivot 的值
		for i < j && arr[i] <= pivot {
			i++
		}
		arr[j] = arr[i]
	}
	arr[i] = pivot

	// 递归排序左右两部分
	quickSort(arr, left, i-1)
	quickSort(arr, i+1, right)
}

//字符串反转
func reverseString(s string) string {
	runes := []rune(s) // 将字符串转换为 rune 切片，避免中文乱码
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

//合并两个有序列表
func mergeSortedSlices(a, b []int) []int {
	result := make([]int, 0, len(a)+len(b))
	i, j := 0, 0

	for i < len(a) && j < len(b) {
		if a[i] < b[j] {
			result = append(result, a[i])
			i++
		} else {
			result = append(result, b[j])
			j++
		}
	}

	// 添加剩余元素
	result = append(result, a[i:]...)
	result = append(result, b[j:]...)

	return result
}
